package ToYesterday.RebuildTree;

class Node {
    int data;
    Node lchild;
    Node rchild;

    public Node(int data, Node lchild, Node rchild) {
        this.data = data;
        this.lchild = lchild;
        this.rchild = rchild;
    }
}

public class Solution {

    public static Node solution(int[] strs1, int[] strs2) {
        Node T = new Node(strs1[0], null, null);
        Node p = T;
        ensureTnode(strs1, strs2, p, 0, 0, strs2.length - 1);
        return T;
    }

    public static void ensureTnode(int[] strs1, int[] strs2, Node p, int Tnum, int start, int stop) {
        if (start == stop) return;
        int i = 0;
        for (i = 0; strs2[i] != p.data; i++) ;
        int leftNums = i - start;
        int rightNums = stop - i;
        if (leftNums > 0) {
            p.lchild = new Node(strs1[Tnum + 1], null, null);
        }

        if (rightNums > 0) {
            p.rchild = new Node(strs1[Tnum + leftNums + 1], null, null);
        }
        if (p.lchild!=null)
        ensureTnode(strs1, strs2, p.lchild, Tnum + 1, i-leftNums, i-1);
        if (p.rchild!=null)
        ensureTnode(strs1, strs2, p.rchild, Tnum + 1 + leftNums, i+1, i+rightNums);
    }

}
